{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## best-time-to-buy-and-sell-stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution {\n",
    "    public int maxProfit(int[] prices) {\n",
    "        int minprice = Integer.MAX_VALUE;\n",
    "        int maxprofit = 0;\n",
    "        for (int price: prices) {\n",
    "            maxprofit = Math.max(maxprofit, price - minprice);\n",
    "             minprice = Math.min(price, minprice);\n",
    "        }\n",
    "        return maxprofit;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "int arr[] = {7, 1, 5, 3, 6, 4};\n",
    "Solution solution = new Solution();\n",
    "System.out.println(solution.maxProfit(arr));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 表示数值的字符串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T16:21+0000",
     "start_time": "2020-08-21T16:21:48.429Z"
    }
   },
   "outputs": [],
   "source": [
    "public boolean isNumeric(String str){\n",
    "    if(str == null || str.length() == 0)\n",
    "        return false;\n",
    "    return str.matches(\"[-+]?\\\\d*(\\\\.\\\\d+)?([eE][-+]?\\\\d+)?\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-21T16:22+0000",
     "start_time": "2020-08-21T16:22:05.964Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n"
     ]
    }
   ],
   "source": [
    "System.out.println(isNumeric(\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 顺时针打印矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-22T15:24+0000",
     "start_time": "2020-08-22T15:24:13.319Z"
    }
   },
   "outputs": [],
   "source": [
    "public ArrayList<Integer> printMatrix(int[][] matrix){\n",
    "    ArrayList<Integer> res = new ArrayList();\n",
    "    if(matrix == null || matrix.length == 0) return res;\n",
    "    int rowBegin = 0;\n",
    "    int rowEnd = matrix.length - 1;\n",
    "    int colBegin = 0;\n",
    "    int colEnd = matrix[0].length - 1;\n",
    "    \n",
    "    while(rowBegin <= rowEnd && colBegin <= colEnd) {\n",
    "        // Traverse Right\n",
    "        for(int i = colBegin; i <= colEnd; ++i) {\n",
    "            res.add(matrix[rowBegin][i]);\n",
    "        }\n",
    "        rowBegin++;\n",
    "        // Traverse Down\n",
    "        for(int i = rowBegin; i <= rowEnd; ++i) {\n",
    "            res.add(matrix[i][colEnd]);\n",
    "        }\n",
    "        colEnd--;\n",
    "        // Traverse Left\n",
    "        if(rowBegin <= rowEnd) {\n",
    "            for(int i = colEnd; i >= colBegin; i--) {\n",
    "                res.add(matrix[rowEnd][i]);\n",
    "            }\n",
    "            rowEnd--;\n",
    "        }\n",
    "        // Traver Up\n",
    "        if(colBegin <= colEnd) {\n",
    "            for(int i = rowEnd; i >= rowBegin; i--) {\n",
    "                res.add(matrix[i][colBegin]);\n",
    "            }\n",
    "            colBegin++;\n",
    "        }\n",
    "    }\n",
    "    return res;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-22T15:24+0000",
     "start_time": "2020-08-22T15:24:16.593Z"
    }
   },
   "outputs": [],
   "source": [
    "ArrayList<Integer> ret = new ArrayList();\n",
    "\n",
    "int[][] data = {\n",
    "    {1,2,3,4},\n",
    "    {5,6,7,8},\n",
    "    {9,10,11,12},\n",
    "    {13,14,15,16}\n",
    "};\n",
    "\n",
    "ret = printMatrix(data);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-22T15:24+0000",
     "start_time": "2020-08-22T15:24:18.808Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]\n"
     ]
    }
   ],
   "source": [
    "System.out.println(ret)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 调整数组顺序使奇数位于偶数前面"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-23T13:45+0000",
     "start_time": "2020-08-23T13:45:15.732Z"
    }
   },
   "outputs": [],
   "source": [
    "public void reOrderArray(int[] nums){\n",
    "    int oddCount = 0;   //奇数个数\n",
    "    for(int i:nums){\n",
    "        if(!isEven(i))\n",
    "            oddCount++;\n",
    "    }\n",
    "    int[] copy = nums.clone();\n",
    "    int i = 0,j = oddCount;\n",
    "    for(int num:copy){\n",
    "        if(num%2 == 1)\n",
    "            nums[i++] = num;\n",
    "        else\n",
    "            nums[j++] = num;\n",
    "    }\n",
    "}\n",
    "\n",
    "private boolean isEven(int x){\n",
    "    return x%2 == 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-23T13:48+0000",
     "start_time": "2020-08-23T13:48:09.059Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 5 2 4 "
     ]
    }
   ],
   "source": [
    "int[] data = {1,2,3,4,5};\n",
    "reOrderArray(data);\n",
    "for (int i:data)\n",
    "    System.out.printf(i+\" \");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "方法二：使用冒泡思想，每次都将当前偶数上浮到当前最右边。时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-23T13:53+0000",
     "start_time": "2020-08-23T13:53:37.481Z"
    }
   },
   "outputs": [],
   "source": [
    "public void reOrderArray(int[] nums){\n",
    "    int lenData = nums.length;\n",
    "    for(int i = lenData-1; i > 0; i--){\n",
    "        for(int j = 0; j < i; j++){\n",
    "            if(isEven(nums[j]) && !isEven(nums[j+1])){\n",
    "                swap(nums, j, j+1);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "private boolean isEven(int x){\n",
    "    return x%2 == 0;\n",
    "}\n",
    "\n",
    "private void swap(int[] nums, int i, int j){\n",
    "    int t = nums[i];\n",
    "    nums[i] = nums[j];\n",
    "    nums[j] = t;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-23T13:53+0000",
     "start_time": "2020-08-23T13:53:48.574Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 5 2 4 "
     ]
    }
   ],
   "source": [
    "int[] data = {1,2,3,4,5};\n",
    "reOrderArray(data);\n",
    "for (int i:data)\n",
    "    System.out.printf(i+\" \");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数组中出现次数超过一半的数字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-24T14:37+0000",
     "start_time": "2020-08-24T14:37:15.466Z"
    }
   },
   "outputs": [],
   "source": [
    "public int MoreThanHalfNum_Solution(int[] nums) {\n",
    "    int majority = nums[0];\n",
    "    for (int i = 1, cnt = 1; i < nums.length; i++) {\n",
    "        cnt = nums[i] == majority ? cnt + 1 : cnt - 1;\n",
    "        if (cnt == 0) {\n",
    "            majority = nums[i];\n",
    "            cnt = 1;\n",
    "        }\n",
    "    }\n",
    "    int cnt = 0;\n",
    "    for (int val : nums)\n",
    "        if (val == majority)\n",
    "            cnt++;\n",
    "    return cnt > nums.length / 2 ? majority : 404;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-08-24T14:46+0000",
     "start_time": "2020-08-24T14:46:05.104Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "404\n"
     ]
    }
   ],
   "source": [
    "int[] data = {4,3,4,3,4,3,4,3,1};\n",
    "System.out.println(MoreThanHalfNum_Solution(data));"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.8+10-post-Ubuntu-0ubuntu120.04"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
